using System;
using System.Collections.Generic;
using Gameplay.PVE.Data;
using UnityEngine;
using UnityEngine.UIElements;
using Random = UnityEngine.Random;

namespace Gameplay.PVE
{
    public class PveRoadPath
    {
        public int id;
        private List<Point> points = new List<Point>();//点
        private List<List<float>> edges = new List<List<float>>();//邻接矩阵
        private Dictionary<int,Dictionary<int,Road>> roadList = new Dictionary<int,Dictionary<int,Road>>();//roadList[x][y]表示从x到y的寻路结果
        private bool inited = false;

        private void InitEdge()
        {
            for (int i = 0; i < points.Count; i++)
            {
                var list = new List<float>();
                for (int j = 0; j < points.Count; j++)
                {
                    if (j == i)
                    {
                        list.Add(0);
                    }
                    else
                    {
                        list.Add(float.MaxValue);
                    }
                }
                edges.Add(list);
            }
        }
        
        private void InitGraphByType(int id)
        {
            this.id = id;
            points.Clear();
            edges.Clear();
            
            if (id == 0)
            {
                float crossOffset = 3.6f;
                float roadMax = 10;
                bool isBoth = true;
                points.Add(new Point(0,new Vector3(-crossOffset,0,-crossOffset)));
                points.Add(new Point(1,new Vector3(-crossOffset,0,crossOffset)));
                points.Add(new Point(2,new Vector3(crossOffset,0,crossOffset)));
                points.Add(new Point(3,new Vector3(crossOffset,0,-crossOffset)));
            
                points.Add(new Point(4,new Vector3(-crossOffset,0,- roadMax)));
                points.Add(new Point(5,new Vector3(crossOffset,0,- roadMax)));
                points.Add(new Point(6,new Vector3( roadMax,0,-crossOffset)));
                points.Add(new Point(7,new Vector3( roadMax,0,crossOffset)));
                points.Add(new Point(8,new Vector3(crossOffset,0, roadMax)));
                points.Add(new Point(9,new Vector3(-crossOffset,0, roadMax)));
                points.Add(new Point(10,new Vector3(- roadMax,0,crossOffset)));
                points.Add(new Point(11,new Vector3(- roadMax,0,-crossOffset)));

                InitEdge();
                
                AddEdge(0,1,isBoth);
                AddEdge(1,2,isBoth);
                AddEdge(2,3,isBoth);
                AddEdge(3,0,isBoth);
            
                AddEdge(0,4,isBoth);
                AddEdge(3,5,isBoth);
                AddEdge(1,9,isBoth);
                AddEdge(2,8,isBoth);
                AddEdge(10,1,isBoth);
                AddEdge(11,0,isBoth);
                AddEdge(2,7,isBoth);
                AddEdge(3,6,isBoth);
                inited = true;
            }
            else if (id == 1)
            {
                float crossOffset = 1f;
                float roadMax = 15;
                bool isBoth = false;
                points.Add(new Point(0,new Vector3(-crossOffset,0,-crossOffset)));
                points.Add(new Point(1,new Vector3(-crossOffset,0,crossOffset)));
                points.Add(new Point(2,new Vector3(crossOffset,0,crossOffset)));
                points.Add(new Point(3,new Vector3(crossOffset,0,-crossOffset)));
            
                points.Add(new Point(4,new Vector3(-crossOffset,0,- roadMax)));
                points.Add(new Point(5,new Vector3(crossOffset,0,- roadMax)));
                points.Add(new Point(6,new Vector3( roadMax,0,-crossOffset)));
                points.Add(new Point(7,new Vector3( roadMax,0,crossOffset)));
                points.Add(new Point(8,new Vector3(crossOffset,0, roadMax)));
                points.Add(new Point(9,new Vector3(-crossOffset,0, roadMax)));
                points.Add(new Point(10,new Vector3(- roadMax,0,crossOffset)));
                points.Add(new Point(11,new Vector3(- roadMax,0,-crossOffset)));

                InitEdge();
                
                AddEdge(1,0,isBoth);
                AddEdge(2,1,isBoth);
                AddEdge(3,2,isBoth);
                AddEdge(0,3,isBoth);
            
                AddEdge(0,4,isBoth);
                AddEdge(5,3,isBoth);
                AddEdge(9,1,isBoth);
                AddEdge(2,8,isBoth);
                AddEdge(1,10,isBoth);
                AddEdge(11,0,isBoth);
                AddEdge(7,2,isBoth);
                AddEdge(3,6,isBoth);
                inited = true;
            }
        }
        
        public void InitData(int id)
        {
            if (inited)
            {
                return;
            }
            InitGraphByType(id);
            
            roadList.Clear();
            for (int i = 0; i < points.Count; i++)
            {
                Dijkstra(i);
            }
        }

        /*public void SetGraph(PveMapGraph graph)
        {
            if (inited)
            {
                return;
            }
            points.Clear();
            edges.Clear();
            for (int i = 0; i < graph.points.Count; i++)
            {
                points.Add(new Point(i,graph.points[i]));
            }
            InitEdge();
            for (int i = 0; i < graph.road.Count; i++)
            {
                AddEdge((int)graph.road[i].x,(int)graph.road[i].y);
            }
            roadList.Clear();
            for (int i = 0; i < points.Count; i++)
            {
                Dijkstra(i);
            }
        }*/
        
        private void Dijkstra(int start)
        {
            Dictionary<int,Road> roads = new Dictionary<int, Road>();
            Dictionary<int,bool> flagDic = new Dictionary<int, bool>();
            Dictionary<int, int> prevDic = new Dictionary<int, int>();
            Dictionary<int, float> distanceDic = new Dictionary<int, float>();
            //初始化
            for (int i = 0; i < points.Count; i++)
            {
                flagDic.Add(i,false);
                float distance = edges[start][i] != 0 ? edges[start][i] : float.MaxValue;
                prevDic.Add(i,distance == float.MaxValue ? 0 : start);
                distanceDic.Add(i,distance);
            }

            flagDic[start] = true;
            distanceDic[start] = 0;
           
            for (int i = 1; i < points.Count; i++)
            {
                float min = float.MaxValue;
                int minIndex = -1;

                for (int j = 0; j < points.Count; j++)
                {
                    //再没有获取最短路径的顶点里找到最近的
                    if (!flagDic[j] && distanceDic[j] < min)
                    {
                        min = distanceDic[j];
                        minIndex = j;
                    }
                }

                if (minIndex == -1)
                {
                    continue;
                }
                
                //该点标记为获取过最短路径
                flagDic[minIndex] = true;
                
                //prevDic[minIndex] = start;
                for (int j = 0; j < points.Count; j++)
                {
                    try
                    {
                        float d = edges[minIndex][j] == float.MaxValue ? float.MaxValue : min + edges[minIndex][j];
                        if (!flagDic[j] && d < distanceDic[j])
                        {
                            distanceDic[j] = d;
                            //标记前一个节点
                            prevDic[j] = minIndex;
                        }
                    }
                    catch (Exception e)
                    {
                        Console.WriteLine(e);
                        throw;
                    }
                    
                }
            }

            //把结果存到字典里，用于查找路径点
            for (int i = 0; i < points.Count; i++)
            {
                List<int> list = new List<int>();
                int index = i;
                int count = 0;
                while (index != start)
                {
                    list.Insert(0,index);
                    index = prevDic[index];
                    if (index == i)
                    {
                        break;
                    }
                    count++;
                    if (count > prevDic.Count)
                    {
                        //说明该起点没有路径
                        break;
                    }
                }
                list.Insert(0,start);
                roads.Add(i,new Road
                {
                    distance = distanceDic[i],
                    points = list,
                });
            }
            roadList.Add(start,roads);
        }
        
        //isBoth表示是否双向联通
        private void AddEdge(int start, int end,bool isBoth = true)
        {
            float distance = Vector3.Distance(points[start].position, points[end].position);
            edges[start][end] = distance;
            if (isBoth)
            {
                edges[end][start] = distance;
            }
            /*points[start].edges.Add(new Edge
            {
                startIndex = start,
                endIndex = end,
                distance = distance,
            });
            points[end].edges.Add(new Edge
            {
                startIndex = end,
                endIndex = start,
                distance = distance,
            });*/
        }

        public List<Vector3> GetRandomRoadPath()
        {
            int startIndex = Random.Range(0, points.Count);
            int endIndex = Random.Range(0, points.Count);
            return GetPath(startIndex, endIndex,Vector3.zero);
        }

        public int GetClosedPoint(Vector3 point)
        {
            float distance = float.MaxValue;
            int closedIndex = 0;
            for (int i = 0; i < points.Count; i++)
            {
                var d = Vector3.Distance(point, points[i].position);
                if (distance > d)
                {
                    distance = d;
                    closedIndex = i;
                }
            }
            return closedIndex;
        }

        public List<Vector3> GetRandomPathByStartPoint(Vector3 point,Vector3 offset)
        {
            int startIndex = GetClosedPoint(point-offset);
            List<int> endCandidates = new List<int>();
            foreach (var item in roadList[startIndex])
            {
                if (item.Value.distance < float.MaxValue)
                {
                    endCandidates.Add(item.Key);
                }
            }
            int endIndex = endCandidates[Random.Range(0, endCandidates.Count)];
            var list = GetPath(startIndex, endIndex,offset);
            list.Insert(0,point);
            return list;
        }


        
        //找到距离起点和终点最近的2个点，返回路径
        public List<Vector3> GetPathByStartAndEnd(Vector3 start, Vector3 end,Vector3 offset)
        {
            int startIndex = GetClosedPoint(start - offset);
            int endIndex = GetClosedPoint(end - offset);
            var list = GetPath(startIndex, endIndex, offset);
            if (list.Count > 0 && Vector3.Distance(list[0],start) < 0.2f)
            {
                
            }
            else
            {
                list.Insert(0,start);
            }
            
            if (list.Count > 0 && Vector3.Distance(list[list.Count - 1],end) < 0.2f)
            {
                
            }
            else
            {
                list.Add(end);
            }
            
            return list;
        }

        //根据起点和终点找到通往最终点的最短路径
        public List<Vector3> GetShortestPathByStartAndEnd(Vector3 start,Vector3 end,Vector3 offset)
        {
            int endIndex = GetClosedPoint(end - offset);
            float distance = float.MaxValue;
            int startIndex = -1;
            for (int i = 0; i < points.Count; i++)
            {
                float pathDistance = roadList[i][endIndex].distance;
                if (i == endIndex || pathDistance == float.MaxValue)
                {
                    continue;
                }
                
                var d = Vector3.Distance(start, points[i].position) + pathDistance;
                if (d < distance)
                {
                    distance = d;
                    startIndex = i;
                }
            }

            if (startIndex != -1)
            {
                var list = GetPath(startIndex, endIndex, offset);
                list.Insert(0,start);
                list.Add(end);
                return list;
            }
            else
            {
                Debug.Log("未找到最短路径");
                return GetPathByStartAndEnd(start, end, offset);
            }
        }
        
        public List<Vector3> GetPath(int startIndex, int endIndex,Vector3 offset)
        {
            Road road = roadList[startIndex][endIndex];
            List<Vector3> list = new List<Vector3>();
            for (int i = 0; i < road.points.Count; i++)
            {
                list.Add(points[road.points[i]].position + offset);
            }
            return list;
        }
        
        private struct Edge
        {
            public int startIndex;
            public int endIndex;
            public float distance;
        }

        private class Road
        {
            public List<int> points;
            public float distance;
        }

        struct Point
        {
            public int index;
            public Vector3 position;
            //public List<Edge> edges;

            public Point(int index,Vector3 position)
            {
                this.index = index;
                this.position = position;
                //edges = new List<Edge>();
            }
        }
    }
}